In this paper we analyze the average queue backlog in a combined input-outputqueued switch using a maximal size matching scheduling algorithm. We comparethis average backlog to the average backlog achieved by an optimal switch. Wemodel the cell arrival process as independent and identically distributedbetween time slots and uniformly distributed among input and output ports. Forswitches with many input and output ports, the backlog associated with maximalsize matching with speedup 3 is no more than 10/3 times the backlog associatedwith an optimal switch. Moreover, this performance ratio rapidly approaches 2as speedup increases.
展开▼